package m202406.d23;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/23 19:24
 */
public class Q486 {

    public static void main(String[] args) {
        Q486 q486 = new Q486();
        q486.predictTheWinner(new int[]{1, 3, 1});
    }

    public boolean predictTheWinner(int[] nums) {
        int sum = handle(nums, 0, nums.length-1, 0, true);
        int all = 0;
        for (int num : nums) {
            all = all + num;
        }
        return sum >= all / 2.0;
    }

    private int handle(int[] nums, int left, int right, int sum, boolean flag) {
        if (left > right) {
            return sum;
        }
        if (!flag) {
            if(nums[left]<nums[right]){
                return handle(nums,left,right-1,sum,true);
            }else {
                return handle(nums,left+1,right,sum,true);
            }
        } else {
            return Math.max(
                    handle(nums, left + 1, right, sum + nums[left], false),
                    handle(nums, left, right - 1, sum + nums[right], false)
            );
        }
    }
}
